1. Field of Invention
The present invention relates generally to the field of network bandwidth allocation, and specifically in one aspect to maximizing the utilization of available bandwidth on the network to support video services with various bit-rates (such as on-demand video) over a content-based network such as a cable television network.
2. Description of Related Technology
Providing “on-demand” (OD) services, such as e.g., video on-demand or VOD, is well known in the prior art. In a typical configuration, the VOD service makes available to its users a selection of multiple video programs that they can choose from and watch over a network connection with minimum setup delay. At a high level, a VOD system consists of one or more VOD servers that pass and/or store the relevant content; one or more network connections that are used for program selection and program delivery; and customer premises equipment (CPE) to receive, decode and present the video on a display unit. The content is typically distributed to the CPE over a Hybrid Fiber Coaxial (HFC) network.
Depending on the type of content made available and rate structure for viewing, a particular VOD service could be called “subscription video-on-demand (SVOD)” that gives customers on-demand access to the content for a flat monthly fee, “free video-on-demand (FVOD)” that gives customers free on-demand access to some content, “movies on-demand” where VOD content consists of movies only, and so forth. Many of these services, although referred to by names different than VOD, still share many of the same basic attributes including storage, network and decoder technologies.
Just as different varieties of VOD service offerings have evolved over time, several different network architectures have also evolved for deploying these services. These architectures range from fully centralized (e.g., VOD servers at a central location) to fully distributed (e.g., multiple copies of content distributed on VOD servers very close to customer premises), as well as various other network architectures there between. Since most cable television networks today consist of optical fiber towards the “core” of the network which are connected to coaxial cable networks towards the “edge”, VOD transmission network architectures also consist of a mixture of optical fiber and coaxial cable portions.
The CPE for VOD often consists of a digital cable set-top box (DSTB) that provides the functions of receiving cable signals by tuning to the appropriate RF channel, processing the received signal and outputting VOD signals for viewing on a display unit. Such a digital set-top box also typically hosts a VOD application that enables user interaction for navigation and selection of VOD menu.
While the architectural details of how video is transported in the core HFC network can be different for each VOD deployment, each generally will have a transition point where the video signals are modulated, upconverted to the appropriate RF channel and sent over the coaxial segment(s) of the network. Depending on the topology of the individual cable plant, this could be performed at a node, hub or a headend. The coaxial cable portion of the network is variously referred to as the “access network” or “edge network” or “last mile network.”
In U.S. cable systems for example, downstream RF channels used for transmission of television programs are 6 MHz wide, and occupy a 6 MHz spectral slot between 54 MHz and 860 MHz. Deployments of VOD services have to share this spectrum with already established analog and digital cable television services. For this reason, the exact RF channel used for VOD service may differ from plant to plant. However, within a given cable plant, all homes that are electrically connected to the same cable feed running through a neighborhood will receive the same downstream signal. For the purpose of managing VOD services, these homes are grouped into logical groups typically called Service Groups. Homes belonging to the same Service Group receive their VOD service on the same set of RF channels.
VOD service is typically offered over a given number (e.g., 4) of RF channels from the available spectrum in cable. Thus, a VOD Service Group consists of homes receiving VOD signals over the same 4 RF channels. Reasons for this grouping include (i) that it lends itself to a desirable “symmetry of two” design of products (e.g. Scientific Atlanta's MQAM), and (ii) a simple mapping from incoming Asynchronous Serial Interface (ASI) payload rate of 213 Mbps to four QAM payload rates.
In most cable networks, VOD programs are transmitted using MPEG (e.g., MPEG-2) audio/video compression. Since cable signals are transmitted using Quadrature Amplitude Modulation (QAM) scheme, available payload bitrate for typical modulation rates (QAM-256) used on HFC systems is roughly 38 Mbps. In many VOD deployments, a typical rate of 3.75 Mbps is used to send one video program at resolution and quality equivalent to NTSC broadcast signals. In digital television terminology, this is called Standard Definition (SD) television resolution. Therefore, use of MPEG-2 and QAM modulation enables carriage of 10 SD sessions on one RF channel (10×3.75=37.5 Mbps<38 Mbps). Since a typical Service Group consists of 4 RF channels, 40 simultaneous SD VOD sessions can be accommodated within a Service Group. These numbers work out very well for many deployment scenarios, such as the following example. A typical “service area” neighborhood served by a coaxial cable drop from the cable network consists of 2000 homes, of which about two-thirds are cable subscribers, of which about one-third are digital cable subscribers, of which about 10% peak simultaneous use is expected. Hence, the bandwidth required to meet VOD requirements is 2000×(⅔)×(⅓)×0.1=approximately 40 peak VOD sessions—the exact number supported by a 4 QAM service group.
From the discussion above, the need for a function called Service Resource Manager (SRM) is evident. When a new VOD session request is made, the SRM receives that request, allocates bandwidth on a downstream QAM channel, and sends the information back to the CPE that made the request so that it can tune to the right RF channel and the VOD program therein. Since the SRM controls mapping of incoming VOD session requests to QAM channels within the Service Group, it is an appropriate place for a Cable Operator to enforce RF channel usage policy. In general, SRM should maximize availability of bandwidth to VOD sessions (by efficiently recycling bandwidth from expired sessions) and by ensuring some level of redundancy in case of equipment failure (e.g. a QAM modulator goes down).
More and more US households are beginning to purchase High Definition (HD) televisions (HDTV). By one estimate, by the end of 2004, over 12 million US households will have HDTV displays. To keep up with the trend, MSOs have begun offering HD television programs to cable customers and have recently started looking into deploying HD VOD services.
Entertainment-quality transmission of HD signals requires about four times as much bandwidth as SD. For an exemplary MPEG-2 Main Profile—High Level (MP@HL) video compression, each HD program requires around 15 Mbps bitrate. Although revenues from HD VOD service may not be four times the revenue from SD VOD service, the ability to offer HD VOD service is often critical to cable operators' strategy to be a leader in digital television service offerings.
Use of MPEG HD compression technology for initial deployment of HD VOD services is a logical choice, as HD VOD shares the same MPEG-2 transport layer technology. This approach allows reuse of most of the infrastructure deployed for SD VOD services. By using MPEG multiplexing techniques, SD and HD video streams can be simultaneously carried over the fiber side of the VOD network and multiplexed onto the same QAM channel in a service group. Since roughly 37.5 Mbps bandwidth is available on one QAM-256 carrier, cable operators can mix and match HD and SD VOD sessions using 3.75 Mbps per SD and 15 Mbps per HD VOD stream. For example, on a single QAM carrier, maximum 2 HD VOD sessions can be offered adding up to an aggregate 30 Mbps, with the other 7.5 Mbps being used by 2 SD sessions.
It should be recognized that under prevailing network and CPE design practices, the bandwidth required by a video stream cannot be spread over two QAM carriers. For example, when a new HD VOD session request is granted, all 15 Mbps of bandwidth must be made available on a single QAM carrier.
The role of the aforementioned SRM becomes even more important when managing a Service Group for simultaneous HD and SD VOD sessions. It has the additional task to map VOD sessions to QAM carriers such that it can ensure sufficient bandwidth block for HD VOD session on a QAM carrier in that Service Group. The method used for this mapping should at the same time be able to maximize the amount of bandwidth used without leaving bandwidth stranded on a QAM carrier. Since HD VOD takes much more bandwidth that SD video, during the introduction phase, a cable operator may wish to limit maximum number of sessions of either kind (SD or HD) allowed within a Service Group. Clearly, this number should be easily changeable (upward or downward) if business economics or other considerations demand it.
The foregoing discussion makes no assumptions regarding specific implementation details of the SRM. It will be recognized that the SRM function can be implemented at the edge or core of the network, in a VOD server, or elsewhere. Depending on where this function is implemented, it is variously referred to as NSG (Network Services Gateway) and SRM (Service Resource Manager).
For example, in a Scientific Atlanta network, the VOD server acts as the session resource manager and asks the Digital Network Control System (DNCS) for specific resources. The DNCS responds with a negative or positive response to the request and the VOD server implements the appropriate logic based on the response.
The need for a function that assigns from an available pool of resources to an incoming resource requests is known in the prior art. Various methods have been proposed to perform this function.
For example, U.S. Pat. No. 6,434,141 to Oz, et al. issued Aug. 13, 2002 and entitled “Communication management system and method” discloses a broadband multimedia system including a communication bus, a router, connected to the communication bus and further between a plurality of media sources and a plurality of network transmitters, a session manager, connected to communication bus, where the session manager provides routing instructions to the router, for directing data received from the media sources to the network transmitters for transmitting over a broadband network. No disclosure regarding assignment of bandwidth to VOD session requests is provided.
U.S. Pat. No. 6,201,901 to Imajima, et al. issued Apr. 3, 2001 and entitled “Video data distributing device by video on demand” discloses a requested title recognizing mechanism recognizes the title of a video requested by the subscriber. A VOD service state monitoring mechanism determines whether or not the broadcast of the video is to be provided in the FVOD or the NVOD service, and if there is any available channel for the broadcast. If the broadcast has not been switched from the FVOD service to the NVOD service, then a busy state monitoring mechanism checks the number of the current simultaneous subscribers for the video. If the number is equal to or larger than a threshold, then the busy state monitoring mechanism instructs an NVOD service providing mechanism to broadcast the requested video in the NVOD service. If the number is smaller than the threshold, then the busy state monitoring mechanism instructs an FVOD service providing mechanism to broadcast the requested video in the FVOD service. The patent does not, however, disclose any details regarding RF channel selection from available channels, or assignment of channels to the VOD request.
U.S. Pat. No. 6,169,728 to Perreault, et al. issued Jan. 2, 2001 and entitled “Apparatus and method for spectrum management in a multipoint communication system” discloses an apparatus and method for spectrum management in a multipoint communication system that controls upstream channel usage for secondary stations transmitting information to a primary station and downstream channel usage for secondary stations receiving information from a primary station. The apparatus includes a processor arrangement having a master controller and a plurality of processors, with the processor arrangement connected to a channel interface. The apparatus and method controls channel load balancing, channel congestion, and channel assignment in a multipoint communication system, and controls upstream channels independently from downstream channels. Factors and parameters utilized in such channel control and allocation include error parameters, channel noise parameters, transmit and receive loading factors, and congestion parameters. The patent also discloses implementation of “Least-Loaded” algorithm to assign bandwidth for next session request to the Least-Loaded carrier.
U.S. Pat. No. 6,092,178 to Jindal, et al issued Jul. 18, 2000 and entitled “System for responding to a resource request” discloses a method wherein a trigger is provided in association with a network naming service, such as DNS (Domain Name Service) that handles client requests for an application. The trigger comprises a set of executable instructions referenced by a resource record associated with an identifier of the application. In response to a client request concerning the application, the resource record is retrieved and the instructions are executed. In one implementation of a trigger, a DNS server provides load balancing among a plurality of servers within a network name space (e.g., domain or sub-domain) offering an application program (or replicated service) that is known by a virtual server name. A policy is selected for choosing a preferred server from the plurality of servers according to a specified status or operational characteristic of the application instances, such as the Least-Loaded instance of the application or the instance with the fastest response time. The policy is encapsulated within multiple levels of objects or modules distributed among the plurality of servers and the DNS server. The objects collect and assemble the servers' status and operational characteristics. The information collected by the objects is analyzed to select the server that best satisfies the selected policy. A client request for the application is received by the DNS server, which retrieves a resource record corresponding to the virtual server name. Within the record is the name of a trigger. The trigger is executed to select, or retrieve an identity of, a server to which the client request is to be directed.
U.S. Pat. No. 6,687,735 to Logston, et al. issued Feb. 3, 2004 and entitled “Method and apparatus for balancing distributed applications” discloses a method and apparatus for balancing distributed applications within a client/server network, such as a cable television network. In one aspect, a method of balancing the load of distributed application client portions (DACPs) across various server portions (DASPs) and server machines is disclosed. Statistics are maintained by one or more software processes with respect to the available resources of the servers and their loading; new process threads and/or distributed application server portions are allocated across the servers to maintain optimal system performance as client device loading increases or changes. In another aspect of the invention, an object-oriented distributed application software architecture employing both vertical and horizontal partitions and “mutable” (i.e., transportable) objects is disclosed. The mutable objects may reside on either the server or client portions of the distributed application while maintaining at least one network partition. A runtime environment adapted for the operation of the foregoing object-oriented distributed application, including a message protocol useful for interprocess communication, is also disclosed. Methods for downloading the DACP from the servers, and scaling the DACP at download based on client device configuration, are further disclosed.
The SeaChange MediaCluster Server device manufactured by SeaChange International Corporation comprises a group of fault-resilient VOD servers connected over a network, in effect acting as one server. See, e.g., U.S. Pat. No. 5,862,312 to Mann, et al. issued Jan. 19, 1999 and entitled “Loosely coupled mass storage computer cluster” and its progeny. This patent discloses a method and apparatus redundantly store data, in particular video data objects, in a distributed computer system having at least three processor systems, each processor system being connected in point to point two way channel interconnection with each other processor system. The data is stored in a redundant fashion both at the computer system level as well as the processor system level. Accordingly, the failure of a single processor does not adversely affect the integrity of the data. The computer system can also overlay a switching system connected in a ring fashion for providing a fault tolerance to the failure of a single connected processor system at the switch level.
The SeaChange apparatus further includes a session resource manager (SRM), and associated connection manager (CM) and streaming service (SS). The CM ostensibly allocates bandwidth, selecting the best network delivery path over which to stream data to the requesting entity. The SS “optimizes” bandwidth and provides some level of fail-over behavior, such that software component failure will not necessarily cause loss or tear-down of the underlying sessions. No functionality relating to the selective evaluation of allocation of bandwidth based on different service levels (e.g., SD or HD) is provided within this apparatus, however.
Description and Limitations of Least- and Most-Loaded Algorithms
Consider now the case of SD only VOD requests as shown in FIG. 1. The Service Group is assumed to have 4 QAM channels available. The first column 102 titled QAM1 corresponds to the first QAM carrier allocated to the VOD service. The column is divided into 10 rows, each representing 3.75 Mbps bandwidth available within the total capacity of the carrier. The corresponding aggregate bandwidth used up when each block is assigned to a VOD session is shown in the rightmost column 110 titled “QAM Bandwidth Mbps.” From bottom to top, as the number of blocks assigned to VOD sessions increases, the total bandwidth used increases in steps of 3.75 Mbps from 3.75 Mbps (first session) to 37.5 (10th session). Similar bitrate blocks for three other QAM carriers belonging to the same service group are shown in the columns 104, 106 and 108 (QAM2, QAM3 and QAM4 respectively). The number in each box in FIG. 1 comprises a session index corresponding to a VOD session that is currently active.
In case of the Least-Loaded algorithm, every next VOD session request is granted bandwidth on the QAM that has the least bandwidth being used by VOD services (i.e. most free bandwidth available) with the search starting in a fixed sequence. For example, in FIG. 1, the following sequence is assumed for bandwidth search QAM1→QAM2→QAM3→QAM4. As shown in FIG. 1, first VOD request is assigned to QAM1, second request addressed to QAM2, third request is assigned to QAM3, fourth request is assigned to QAM4 and the 5th request is assigned by coming back to QAM1 and so on. Therefore, QAM session index number goes up from the bottom row left to right to top row, left to right in each row.
FIG. 2 is shows how the prior art Least-Loaded algorithm approach can leave HD VOD bandwidth stranded. In this example, a number (e.g., 28) consecutive SD VOD session requests are received, followed by a second number (e.g., 3) of HD VOD requests. The first twenty-eight SD VOD requests are allocated evenly on the four QAMs 202, 204, 206, 208 as shown in FIG. 2. The frequency slots remaining after the 28th session are assigned the remaining bandwidth 210. This illustrates that the total bandwidth available in this service groups is 45 Mbps (12 slots of 3.75 Mbps each). However, since the bandwidth available in each QAM is only 11.25 Mbps, which is below HD_BANDWIDTH, and since a HD VOD session cannot be allocated bandwidth split over multiple QAMs, the SRM will not be able to grant bandwidth to an incoming HD VOD request. The 45 Mbps available is therefore left “stranded” for the purpose of granting HD VOD sessions. This highlights the limitation of the Least-Loaded algorithm in that it lacks a systematic method of bandwidth allocation to ensure high availability of bandwidth in the Service Group to enable HD VOD sessions. A bandwidth allocation algorithm that can maximize usage of bandwidth usage should be able to make the remaining 45 Mbps bandwidth to three HD VOD sessions (at 15 Mbps per session.)
In the case where HD VOD session requests occur earlier, the Least-Loaded algorithm will eventually leave bandwidth stranded for HD VOD sessions. This is shown in the example of FIG. 3, the first two sessions 310, 312 are allocated bandwidth on QAM1 302 and QAM2 304, respectively. The next twenty-two sessions are SD, and are allocated bandwidth using Least-Loaded algorithm. The available bandwidth resources are now distributed as follows—7.5 Mbps each on QAM1 302 and QAM2 304, 11.25 Mbps on QAM3 306, and 11.25 Mbps on QAM4 308. It can be seen again that although total available bandwidth can support 3 HD VOD sessions, due to splitting the bandwidth among different QAMs, not even a single HD VOD session can be granted bandwidth at this time.
With reference to FIG. 4, the use of Most-Loaded algorithm is now explained. The leftmost column is QAM1 402, corresponding to the first QAM carrier belonging to the VOD Service Group. This column represents the total bandwidth available on this particular QAM carrier and divided into 10 rows, each representing 3.75 Mbps bandwidth available within the QAM carrier. The corresponding aggregate bandwidth used up when each block is assigned to a VOD session is shown in the right-hand column 410. From bottom to top, as the number of blocks assigned to VOD sessions increases, the total bandwidth used increases in steps of 3.75 Mbps from 3.75 Mbps (first session) to 37.5 (10th session). Similar bit-rate blocks for the three other QAM carriers 404, 406, 408 belonging to the same service group are shown (QAM2, QAM3 and QAM4, respectively).
When granting bandwidth using Most-Loaded algorithm, every next VOD session request is granted bandwidth on the QAM that has the least bandwidth available (but enough to accommodate the VOD session). In other words, the bandwidth is granted on the Most-Loaded QAM. FIG. 4 shows the case when the entire bandwidth available to the service group is filled by SD VOD sessions. The 1st session is granted bandwidth on QAM1 402. For the 2nd-10th session requests, since QAM1 402 is Most-Loaded, they are granted bandwidth on QAM1. The 11th session request is granted bandwidth on the next available QAM as QAM1 is fully occupied. Therefore, FIG. 4 shows the session index increasing from 1 to 40 from bottom-left slot, from bottom to top and then to the next QAM (QAM2 404, QAM3 406, and QAM4 408, respectively).
While prior art Most-Loaded algorithm does not exhibit the stranded bandwidth deficiency of the Least-Loaded algorithm previously described, it does have a salient drawback; specifically in the case of a QAM failure. Since the Most-Loaded algorithm unevenly loads up a QAM, a service outage can spread over multiple customers. Furthermore, when HD and SD VOD services are co-mingled, this assignment cannot effectively spread HD VOD sessions over multiple QAMs, thereby detracting from the failure performance that could be achieved if such spreading were utilized. This inadequacy is highlighted in FIGS. 5 and 6.
In FIG. 5, the VOD session request scenario of FIG. 1 above is again considered, yet this time by allocating session requests using the Most-Loaded algorithm. As shown, first twenty-eight SD VOD requests are stacked up by completely filling up QAM1 502, QAM2 504 and part of QAM3 506. The remaining bandwidth is available for two SD VOD sessions 530 on QAM3 506. As shown in FIG. 5, QAM4 508 has enough remaining bandwidth to grant to two HD VOD streams. However, both of these HD VOD streams (if granted) will occupy the same QAM channel, thereby increasing the risk of VOD session outage if that QAM fails.
In FIG. 6, the VOD session request scenario of FIG. 2 is again considered. Per the Most-Loaded algorithm, the first two HD VOD requests 640, 642 are assigned to QAM1 602. Similarly, session requests 25 and 28 are assigned to QAM4 608. It is evident from the session assignments that while QAM1 602 and QAM4 608 are double-loaded with two HD VOD sessions each, none is carried by QAM2 604 and QAM3 606.
While the prior art referenced above has generally identified the “SRM” function and the use of Least- and Most-Loaded algorithms for allocation, it fails to provide any apparatus or method that minimizes or mitigates the stranding of bandwidth in a QAM channel for an HD VOD session when both HD and SD session requests are present, or addresses the other disabilities highlighted above including increased risk of VOD session outage. Furthermore, the prior art SRMs and algorithms do not allow selective implementation of one or more business policies with the network, or even within a single service group.
Hence, there is a need for improved apparatus and methods that both increase the likelihood of having the capacity to provide HD bandwidth within a Service Group to an HD VOD session request, and minimize the chances of stranding bandwidth. Ideally, such apparatus and methods would be adapted to optimize load balancing across QAM channels, as well as maximize HD session support. Such apparatus and methods would further be configured to spread HD VOD sessions across different QAM channels so as to minimize impact of QAM failures on VOD sessions. Mechanisms to manage the maximum allowed number of HD and sessions within a VOD Service Group, and implement business rules and guarantee service levels for both SD and HD sessions, would also be provided.